// test.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
/*
* 456. 132 模式
date:20210325 pm15:58

*/
#include<math.h>
#include <iostream>
#include <vector>
#include <stack>
#include<queue>
using namespace std;
class Solution {
public:
	int min(int a, int b)
	{
		if (a > b)
		{
			return b;

		}
		else
		{
			return a;
		}
	}

	bool find132pattern(vector<int>& nums)
	{//x号位分别代表132的相对位置。
		int i, j;
		int now_min;
		int len = nums.size();
		int* left_min = new int[len];

		//建立单调栈
		stack<int> s1;
		//小于3直接不考虑
		if (len < 3)
		{
			return 0;
		}

		//第i点及左边的最小找出放在left_min[i]
		for (i = 0; i < len; i++)
		{
			
			if (i == 0)
			{
				left_min[i] = nums[i];
				now_min = left_min[i];
			}
			else
			{
				//有新的就更新
				if (now_min > nums[i])
				{	
					now_min = nums[i];
				}
				left_min[i]= now_min;

			}
		}

		//从右边开始遍历
		for (j = len - 1; j > 0; j--)
		{
			//第一个直接放入栈
			if (j == len - 1)
			{
				s1.push(nums[j]);
			}
			else
			{//如果nums[j]> s1.top()，有潜力成为3号位
				if (nums[j] > s1.top())
				{
					//栈顶元素符合2号位要求直接返回1
					if( s1.top() > left_min[j])
					{
						
						return 1;
					}
					else
					{//栈顶元素不符合2号位要求
						//接下来手里拿着nums[j]，把镜头给到栈。
						//从上往下寻找符合2号位的栈顶元素,因为在栈里面的都是已经遍历过的，即没有成为3号位的资格，1号位已经都有了而且是在j的左边根本不关它事。
						//因此不能成为2号位就再见吧
						while (!s1.empty())
						{
							//注意新的栈顶不一定比3号位小，因为它藏在下面的，也可能很大的。
							if (s1.top() > left_min[j]&& nums[j] > s1.top())
							{

								return 1;
							}
							//新栈顶超过三号位了，只能说这次nums[j]很遗憾，没有合适的二号位给你。把栈顶潜力二号位留给下一个更强壮的三号位吧。
							if (nums[j] < s1.top())
							{
								break;
							}
							//你二号位都做不了？再见。
							s1.pop();

						}
						//经过一轮比较，本次的nums[j]三号位无望，有潜力成为2号位。
						s1.push(nums[j]);
						
					}
				}
				else
				{
					//虽然没机会做三号位，有潜力成为2号位
					s1.push(nums[j]);
				}
			}
		}
		//上面如果有就会中断并return 1

		return 0;
	}

};
int main() {
	Solution* s = new Solution();
	vector<int> nums = { 10,12,6,8,3,11 };
	 cout<<s->find132pattern(nums);
}